// #include<bits/stdc++.h>
// using namespace std;
// int js(int x)
// {
//     if(!x) return 0;
//     return (x + 1) / 2;
// }

// int os(int x)
// {
//     return x / 4;
// }

// int main() 
// {
//     int l,r;
//     cin>>l>>r;
//     cout<<js(r) - js(l - 1) + os(r) - os(l - 1);
//     return 0;
// }


// #include<bits/stdc++.h>
// using namespace std;
// long long s[100005],a,ans,t[100005];
// int main()
// {
//     int n,k;
//     cin>>n>>k;
//     for(int i = 1;i <= n;++i)
//     {
//         cin>>a;
//         s[i] = s[i - 1] + a;
//     }
//     for(int i = 0;i <= n;++i)
//     {
//         ans += t[s[i] % k]++;
//     }
//     cout<<ans;
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;

// class t
// {
// public:
//     long long num;
//     int a;
//     int b;
// };

// int main()
// {
//     int n;
//     cin >> n;
//     t tt[1005];
//     for(int i = 0;i < n;++i)
//     {
//         cin >> tt[i].num >> tt[i].a >> tt[i].b;
//     }
//     int m;
//     cin >> m;
//     int mm;
//     for(int i = 0;i < m;++i)
//     {
//         cin >> mm;
//         for(int j = 0;j < n;++j)
//         {
//             if(mm == tt[j].a)
//             {
//                 cout << tt[j].num << " " << tt[j].b << "\n";
//                 break;
//             }
//         }
//     }
//     return 0;
// }


// #include<bits/stdc++.h>
// using namespace std;

// int main()
// {
//     long long n;
//     cin >> n;
//     int arr[n / 2] = {0}, size = 1;
//     int ans = 0, head = 0, temp = 0;
//     // for(int i = 2;i * i < n;++i)
//     // {
//     //     if(n % i == 0)
//     //     {
//     //         arr[size++] = i;
//     //     }
//     // }
//     for(int i = 1;i < size;++i)
//     {
//         if(arr[i] == arr[i - 1] + 1)
//         {
//             temp++;
//         }
//         else
//         {
//             if(temp > ans)
//             {
//                 ans = temp + 1;
//                 temp = 0;
//             }
//         }
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int ans[10];
// int main()
// {
//     int a;
//     while(scanf("%1d", &a) != EOF)
//     {
//         ans[a]++;
//     }
//     for(int i = 0; i < 10; ++i)
//     {
//         if(ans[i] == 0)
//         continue;
//         cout << i << ":" << ans[i] << '\n';
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int is_prime(int n)
// {
// 	int j = 0;
// 	for (j = 2; j <= sqrt(n); j++)
// 	{
// 		if (n % j == 0)
// 		{
// 			return 0;
// 		}
// 	}
// 	return 1;
// }
// int main()
// {
// 	int n = 0;
// 	scanf("%d", &n);
// 	if (is_prime(n))
// 	{
// 		printf("1\n");
// 		printf("%d", n);
// 	}
// 	else
// 	{
// 		int i = 0;
// 		int str = 0;
// 		int len = 0;
// 		for (i = 2; i <= sqrt(n); i++)
// 		{
// 			int ret = 1;
// 			int k = 0;
// 			for (k = i;ret*k<=n;k++)
// 			{
// 				ret *= k;
// 				if (n % ret == 0 && k-i+1>len)
// 				{
// 					str = i;
// 					len = k - i + 1;
// 				}
// 			}
// 		}
// 		printf("%d\n", len);
// 		for (i = str; i < str + len; i++)
// 		{
// 			if (i == str + len - 1)
// 			{
// 				printf("%d", i);
// 			}
// 			else
// 			{
// 				printf("%d*", i);
// 			}
// 		}
// 	}
// 	return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     char s[10][10] =  {{"ling"},{"yi"},{"er"},{"san"},{"si"},{"wu"},{"liu"},{"qi"},{"ba"},{"jiu"}};
//     string ss;
//     cin >> ss;
//     for(int i = 0;ss[i] != '\0';++i)
//     {
//         if(ss[i] == '-')
//         cout << "fu" << " ";
//         else
//         {
//             cout << s[ss[i] - '0'];
//             if(ss[i + 1] != '\0')
//             cout << ' ';
//         }
//     }
//     return 0;
// }



// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int a,b, sum = 0, cnt = 1;
//     cin >> a >> b;
//     for(int i = a; i <= b; i++)
//     {
//         printf("%5d", i);
//         if(cnt % 5 == 0)
//         {
//             printf("\n");
//         }
//         sum += i;
//         cnt++;
//     }
//     if((cnt - 1) % 5 != 0)
//     printf("\n");

//     printf("Sum = %d", sum);
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int l_cmp(const void* e1,const void* e2)
// {
//     int ret = *(long long*)e1 - *(long long*)e2;
//     return ret;
// }
// int main()
// {
//     long long l[3];
//     for(int i = 0; i<3; ++i)
//     {
//         cin >> l[i];
//     }
//     qsort(l,3,sizeof(long long),l_cmp);
//     for(int i = 0; i<3; ++i)
//     {
//         cout << l[i];
//         if(i != 2)
//         {
//             cout << "->";
//         }
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     char a[1000];
//     char b[1000];
//     // scanf("%[^\n]", a);
//     // scanf("%[^\n]", b);
//     gets(a);
//     gets(b);
//     for(int i = 0; a[i] != '\0'; ++i)
//     {
//         int flag = 1;
//         for(int j = 0; b[j] != '\0'; ++j)
//         {
//             if(a[i] == b[j])
//             {
//                 flag = 0;
//                 break;
//             }
//         }
//         if(flag)
//         {
//         printf("%c", a[i]);
//         }
//     }
//     return 0;
// }


// #include <stdio.h>
// #include <math.h>
// int main()
// {
//     int n;
//     scanf("%d",&n);
//     int ans = pow(2,n);
//     printf("2^%d = %d", n, ans);
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int n;
//     cin >> n;
//     int ans = 0;
//     for(int j = 1; j <= n; ++j)
//     {
//         int t = 1;
//         for(int i = 1;i <= j; ++i)
//         {
//             t = t*i;
//         }
//         ans += t;
//     }

//     cout << ans;
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     cout << "This is a simple problem.";
//     return 0;
// }



// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     double a, cnt = 0;
//     char c;
//     cin >> a >> c;
//     double h = (a / 2) + 0.5;
//     for(int i = 0; i < (int)h; ++i)
//     {
//         for(int j = 0; j < a; ++j)
//         {
//             cout << c;
//             cnt++;
//             if(cnt == a)
//             {
//                 cout << "\n";
//                 cnt = 0;
//             }
//         }
//     }
//     return 0;
// }



// #include <bits/stdc++.h>
// using namespace std;
// int q[] = {7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
// char m[] = "10X98765432";
// int main()
// {
//     int n;
//     string s;
//     cin >> n;
//     int flag = 1;
//     for(int i = 0; i < n; ++i)
//     {
//         cin >> s;
//         int sum = 0;
//         for(int j = 0; j < 17; ++j)
//         {
//             if(s[j] == 'X')
//             {
//                 sum += 10 * q[j];
//             }
//             else
//             {
//                 sum += (s[j] - '0') * q[j];
//             }
//         }
//         if( m[sum % 11] != s[17])
//         {
//             cout << s << '\n';
//             flag = 0;
//         }
//     }
//     if(flag)
//     {
//         cout << "All passed";
//     }
//     return 0;
// }



// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     string s;
//     cin >> s;
//     double cnt = 0.0, len = 0.0;
//     int i = 0;
//     for(i = 0; s[i] != '\0'; ++i)
//     {
//         len++;
//         if(s[i] == '2')
//         {
//             cnt++;
//         }
//     }
//     int flag1 = 0,flag2 = 0;
//     if(((s[i - 1] - '0') & 1) == 0)
//     flag2 = 1;

//     if(s[0] == '-')
//     {
//         len--;
//         flag1 = 1;
//     }
//     double ans = cnt / len;
//     if(flag1) ans *= 1.5;
//     if(flag2) ans *= 2.0;
//     ans *= 100;
//     printf("%.2lf", ans);
//     cout << '%';
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int h,m;
//     scanf("%d:%d", &h, &m);
//     int hh = h - 12;
//     if(m > 0) hh++;
//     if(hh > 0)
//     {
//         for (int i = 0;i < hh;++i)
//         {
//             cout << "Dang";
//         }
//     }
//     else
//     {
//         printf("Only %02d:%02d.  Too early to Dang.", h, m);
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int a, b, t;
//     cin >> a >> b;
//     cin >> t;
//     int a1, a2, b1, b2;
//     int aa = 0, bb = 0;
//     for(int i = 0;i < t;++i)
//     {
//         cin >> a1 >> a2 >> b1 >> b2;
//         if((a2 == a1 + b1) && (b2 != a1 + b2))
//         {
//             aa++;
//         }
//         else if(((a2 != a1 + b1) && (b2 == a1 + b2)))
//         {
//             bb++;
//         }
//         if(a == aa)
//         {
//             cout << 'A' << '\n';
//             cout << bb;
//             return 0;
//         }
//         else if(b == bb)
//         {
//             cout << 'B' << '\n';
//             cout << aa;
//             return 0;
//         }
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// char arr[100005];
// int main()
// {
//     int n,k,p;
//     cin >> n;
//     for(int i = 0;i < n;++i)
//     {
//         cin >> k;
//         if(k != 1)
//             for(int j = 0;j < k;++j)
//             {
//                 cin >> p;
//                 arr[p] = 1;
//             }
//         else
//         {
//             cin >> p;
//         }
//     }
//     int m, flag = 1;
//     cin >> m;
//     for(int i = 0;i < m;++i)
//     {
//         cin >> p;
//         if(!arr[p])
//         {
//             printf("%05d", p);
//             if(i < m - 1)
//                 cout << ' ';
//             arr[p] = 1;
//             flag = 0;
//         }
//     }
//     if(flag)
//     {
//         cout << "No one is handsome";
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int n;
//     cin >> n;
//     int t;
//     int j = 0, o = 0;
//     for(int i = 0; i < n; ++i)
//     {
//         cin >> t;
//         if((t & 1) == 1) j++;
//         if((t & 1) == 0) o++;
//     }
//     cout << j << ' ' << o;
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     string s;
//     cin >> s;
//     int g = 0, p = 0, l = 0, t = 0;
//     for(int i = 0; s[i] != '\0'; ++i)
//     {
//         if(s[i] == 'g' || s[i] == 'G')
//         g++;        
//         else if(s[i] == 'p' || s[i] == 'P')
//         p++;        
//         else if(s[i] == 'l' || s[i] == 'L')
//         l++;        
//         else if(s[i] == 't' || s[i] == 'T')
//         t++;
//     }
//     for(;;)
//     {
//         if(g > 0) {cout << 'G'; g--;}
//         if(p > 0) {cout << 'P'; p--;}
//         if(l > 0) {cout << 'L'; l--;}
//         if(t > 0) {cout << 'T'; t--;}
//         if((g == 0) && (p == 0) && (l == 0) && (t == 0)) break;
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int d;
//     cin >> d;
//     if(d == 5)
//     {
//         cout << "7";
//         return 0;
//     }
//     int ans = (d + 2) % 7;
//     cout << ans;
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int zh(string s)//函数 字符串转数字
// {
//     int len = s.length();
//     int sum = 0;
//     for (int i = 0; i < len; i++)
//     {
//         sum += (s[i] - '0')*pow(10, len-i-1);
//     }
//     return sum;
// }
// int main()
// {
//     string A, B;
//     cin >> A;
//     getchar();
//     getline(cin, B);
//     bool tmpA = true, tmpB = true;
//     for (int i = 0; i < A.length(); i++)
//     {
//         if (A[i]-'0'<0 || A[i]-'0'>9)
//         {
//             tmpA = false;
//             break;
//         }
//     }
//     for (int i = 0; i < B.length(); i++)
//     {
//         if (B[i] - '0'<0 || B[i] - '0'>9)
//         {
//             tmpB = false;
//             break;
//         }
//     }
//     if (zh(A)>1000||A[0]=='0')
//     {
//         tmpA = false;
//     }
//     if (zh(B)>1000||B[0]=='0')
//     {
//         tmpB = false;
//     }
//     if (tmpA && tmpB)
//     {
//         cout << A<<" + "<<B<<" = "<<zh(A)+zh(B)<<endl;
//     }
//     if (!tmpA && tmpB)
//     {
//         cout <<  "? + " << B << " = ?" << endl;
//     }
//     if (tmpA && !tmpB)
//     {
//         cout <<A<< " + ? = ?" << endl;
//     }
   
//     if (!tmpA&&!tmpB)
//     {
//         cout << "? + ? = ?";
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int ar[10], arr[10], top = 0;
// int main()
// {
//     string s;
//     cin >> s;
//     for(int i = 0;i < 11; ++i)
//     {
//         ar[s[i] - '0']++;
//     }
//     cout << "int[] arr = new int[]{";
//     int w = 0;
//     for(int i = 0; i < 10; ++i)
//     {
//         if(ar[i]) w++;
//     }
//     int ww = w;
//     for(int i = 9; i >= 0; --i)
//     {
//         if(ar[i])
//         {
//             cout << i;
//             arr[top++] = i;
//             w--;
//             if(w == 0)
//             {
//                 cout << "};" << endl;
//             }
//             else
//             {
//                 cout << ',';
//             }
//         }
//     }
//     cout << "int[] index = new int[]{";
//     for(int i = 0; i < 11; ++i)
//     {
//         int temp = 0;
//         for(int j = 0; j < ww; ++j)
//         {
//             if(arr[j] == (s[i] - '0'))
//             {
//                 cout << j;
//                 if(i != 10)
//                 {
//                     cout << ',';
//                 }
//                 break;
//             }
//         }
//     }
//     cout << "};";
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int n, t;
//     cin >> n;
//     bool flag = 1;
//     for(int i = 0; i < n; ++i)
//     {
//         cin >> t;
//         for(int j = 2; j < sqrt(t); ++j)
//         {
//             if(t % j == 0)
//             {
//                 flag = 0;
//                 break;
//             }
//         }
//         if(flag)
//         {
//             cout << "Yes" << '\n';
//         }
//         else
//         {
//             cout << "No" << '\n';
//         }
//         flag = 1;
//     }
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     double n;
//     cin >> n;
//     double ans = (n - 100) * 0.9 * 2.0;
//     printf("%.1lf", ans);
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;
// char stu[105][15];
// int main()
// {
//     int n;
//     cin >> n;
//     for (int i = 0; i < n; ++i)
//     {
//         cin >> stu[i][0];
//         cin >> &stu[i][1];
//     }
//     for(int i = 0; i < n; ++i)
//     {
//         for(int j = n - 1; j > i; --j)
//         {
//             if(stu[i][0] == '0')
//             {
//                 if(stu[j][0] == '1')
//                 {
//                     cout << &stu[i][1] << ' ';
//                     cout << &stu[j][1] << endl;
//                     stu[j][0] = 2;
//                 }
//             }
//             if(stu[i][0] == '1')
//             {
//                 if(stu[j][0] == '0')
//                 {
//                     cout << &stu[i][1] << ' ';
//                     cout << &stu[j][1] << endl;
//                     stu[j][0] = 2;
//                 }
//             }
//         }
//     }
//     return 0;
// }

// #include<bits/stdc++.h>
// using namespace std;
// int main()
// {
// 	int N,i,temp,a1,b1,a2=0,b2=1,count=0;
//     scanf("%d",&N);
//     for(i=0;i<N;i++)
//     {
//         scanf("%d/%d",&a1,&b1);
//         a2=a1*b2+a2*b1;
//         b2=b1*b2;
//         a1=a2;
//         b1=b2;
//         while(abs(b1)>0)
//         {
//             temp=a1%b1;
//             a1=b1;
//             b1=temp;
//         }
//         a2/=a1;
//         b2/=a1;
//     }
//     if(a2<0)
//     {
//         while(abs(a2)>=b2)
//         {
//             count--;
//             a2+=b2;
//         }
//     }else
//     {
//         while(a2>=b2)
//         {
//             count++;
//             a2-=b2;
//         }
//     }
//     if(count!=0)
//         printf("%d",count);
//     if(count!=0&&a2!=0)
//         printf(" ");
//     if(a2!=0)
//         printf("%d/%d",a2,b2);
//     if(count==0&a2==0)
//         printf("0");
// 	return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;

// int main()
// {
//     int n;
//     cin >> n;
//     double h, w;
//     for(int i = 0; i < n; ++i)
//     {
//         cin >> h >> w;
//         double wanmei = (h - 100) * 0.9 * 2.0;
//         if( fabs(w - wanmei) < wanmei * 0.1)
//         {
//             cout << "You are wan mei!" << endl;
//         }
//         else if((w - wanmei) > wanmei * 0.1)
//         {
//             cout << "You are tai pang le!" << endl;
//         }
//         else
//         {
//             cout << "You are tai shou le!" << endl;
//         }
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {  
//     int n;
//     char c;
//     string s;
//     cin >> n >> c;
//     getline(cin, s);
//     int len = s.size();
//     if(n <= len)
//     {
//         int top = len - n;
//         for(int i = top;i < len; ++i)
//         {
//             cout << s[i];
//         }
//     }
//     else
//     {
//         int m = n - len;
//         for(int i = 0; i < m; ++i)
//         {
//             cout << c;
//         }
//         cout << s;
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int ff[1005];
// int main()
// {
//     int index = 0, n = 0, k = 0, f, max = 0;
//     cin >> n;
//     for(int i = 0; i < n; ++i)
//     {
//         cin >> k;
//         for(int j = 0; j < k; ++j)
//         {
//             cin >> f;
//             ff[f]++;
//             if(ff[f] > max)
//             {
//                 max = ff[f];
//                 index = f;
//             }
//             else if(ff[f] == max)
//             {
//                 if(f > index)
//                 {
//                     index = f;
//                 }
//             }
//         }
//     }
//     cout << index << max;
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     string name, a, b;
//     int n = 0;
//     bool flag1 = 0, flag2 = 0;
//     while(cin >> name)
//     {
//         if(name.size() == 1 && name[0] == '.') break;
//         n++;
//         if(n == 2)
//         {
//             flag1 = 1;
//             a = name;
//         }
//         else if(n == 14)
//         {
//             flag2 = 1;
//             b = name;
//             break;
//         }
//     }
//     if(flag1 && flag2)
//     {
//         cout << a << " and " << b <<" are inviting you to dinner...";
//     }
//     else if(flag1 && !flag2)
//     {
//         cout << a << " is the only one for you...";
//     }
//     else if(!flag1 && !flag2)
//     {
//         cout << "Momo... No one is for you ...";
//     }
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int a, b;
//     cin >> a >> b;
//     cout << a * b;
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     double a, b, ans;
//     cin >> a >> b;
//     ans = a / b;
//     if(b > 0)
//     {
//         printf("%.0lf/%.0lf=%.2lf", a, b, ans);
//     }
//     else if(b < 0)
//     {
//         printf("%.0lf/(%.0lf)=%.2lf", a, b, ans);
//     }
//     else
//     {
//         printf("%.0lf/%.0lf=Error", a, b);
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
// 	int n, len, x, y, r, i, ok = 1;
// 	char a[1010];
// 	char c[1010][1010];
// 	memset(c,' ', sizeof(c));
// 	cin>>n;
// 	getchar();
// 	fgets(a,1010,stdin);
// 	len = strlen(a)-1;
// 	if(len%n != 0) r = len/n+1;
// 	else r = len/n;
// 	for(y = r, i = 0;y >= 1;y--)
// 	{
// 		if(!ok) break;
// 		for(x = 1;x <= n;x++)
// 		{
// 			c[x][y] = a[i++];
// 			if(i == len)
// 			{
// 				ok = 0;
// 				break;
// 			}
// 		}
		
// 	}
// 	for(x = 1;x <= n;x++)
// 	{
// 		for(y = 1;y <= r;y++)
// 		cout<<c[x][y];
// 		cout<<endl; 
// 	}
// 	return 0;
// } 


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int n;
//     cin >> n;
//     char x;
//     double h;
//     for(int i = 0; i < n; ++i)
//     {
//         cin >> x >> h;
//         if(x == 'F')
//         {
//             printf("%.2lf\n", h * 1.09);
//         }
//         else if(x == 'M')
//         {
//             printf("%.2lf\n", h / 1.09);
//         }
//     }
//     return 0;
// }



// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int n = 0;
//     for(int i = 0;;++i)
//     {
//         cin >> n;
//         if(n == 250)
//         {
//             cout << i + 1;
//             break;
//         }
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     string s;
//     cin >> s;
//     cout << &s[6] << '-';
//     s[6] = '\0';
//     cout << s;
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int n;
//     cin >> n;
//     string s;
//     int cnt = 0;
//     for(int i = 0; s != "End"; ++i)
//     {
//         cin >> s;
//         if(s == "End") break;
//         if(cnt % n == 0)
//         {
//             cout << s << endl;
//             cnt = 0;
//             continue;
//         }
//         if(s == "ChuiZi")
//         {
//             cout << "Bu" << endl;
//         }
//         else if(s == "JianDao")
//         {
//             cout << "ChuiZi" << endl;
//         }
//         if(s == "Bu")
//         {
//             cout << "JianDao" << endl;
//         }
//         cnt++;
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     string s;
//     cin >> s;
//     cout << "Hello " << s;
//     return 0;
// }


// #include <iostream>
// #include <math.h>
// using namespace std;
// int main()
// {
//     long long x;
//     cin >> x;
//     long long i = 0;
//     long long g = 1;
//     for(i = 1; ; ++i)
//     {
//         long long ans = g / x;
//         if((g % x) == 0)
//         {
//             cout << ans << ' ' << i;
//             break;
//         }
//         g += pow(10, i);
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     string name;
//     int hx, mb, n;
//     cin >> n;
//     for(int i = 0; i < n; i++)
//     {
//         cin >> name >> hx >> mb;
//         if((hx > 20 || hx < 15) || (mb < 50 || mb > 70))
//         {
//             cout << name << '\n';
//         }
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;

// int func1(int n)
// {
//     if(n <= 1)
//         return n;
//     else
//     {
//         return func1(n - 1) + func1(n - 2);
//     }
// }

// int func2(int n)
// {
//     int fb[100] = {0};
//     fb[0] = fb[1] = 1;
//     for(int i = 2; i < n; ++i)
//     {
//         fb[i] = fb[i - 1] + fb[i - 2];
//     }
//     return fb[n - 1];
// }

// int main()
// {
//     int n;
//     cin >> n;
//     int ans = func1(n);
//     cout << ans;
//     return 0;
// }

// #include <bits/stdc++.h>

// int func(int n)
// {
//     if(n <= 1)
//     {
//         return 1;
//     }
//     else
//     {
//         return n * func(n - 1);
//     }
// }

// using namespace std;
// int main()
// {
//     int n;
//     cin >> n;
//     int ans = func(n);
//     cout << ans;
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;

// int DigitSum(int n)
// {
//     if(n <= 0)
//         return 0;
//     else
//     {
//         int temp = n % 10;
//         cout << temp << '\n';
//         return DigitSum(n / 10);
//     }
// }

// int main()
// {
//     int n;
//     cin >> n;
//     DigitSum(n);
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// class Solution {
// private:
//     int star_i;
//     int star_j;
//     bool ans = false;
//     vector<vector<bool>> path;

//     void dfs(vector<vector<char>>& grid, int x, int y)
//     {
//         int h = grid.size();
//         int l = grid[0].size();
//         if(ans) return;
//         if(path[x][y]) return;
//         path[x][y] = true;
//         for(int i = -1; i <= 1; ++i)
//         {
//             for(int j = -1; j <= 1; ++j)
//             {
//                 if(i == j || (i == 1 && j == -1) || (i == -1 && j == 1)) continue;
//                 int tx = x + i, ty = y + j;
//                 if(tx == star_i && ty == star_j)
//                 {
//                     ans = true;
//                     return;
//                 }
//                 if(tx < h && tx >= 0 && ty < l && ty >=0)
//                 {
//                     if(grid[tx][ty] == grid[x][y])
//                     {
//                         dfs(grid, tx, ty);
//                     }
//                     if(ans) return;
//                 }
//             }
//         }
//     }

// public:
//     bool containsCycle(vector<vector<char>>& grid) {
//         int h = grid.size();
//         int l = grid[0].size();
//         if(h < 2 || l < 2) return false;
//         vector<vector<bool>> path(h, vector<bool>(l, false));
//         this->path = path;
//         for(int i = 0; i < h; ++i)
//         {
//             for(int j = 0; j < l; ++j)
//             {
//                 star_i = i;
//                 star_j = j;
//                 dfs(grid, i, j);
//                 if(ans) return ans;
//             }
//         }
//         return ans;
//     }
// };

// int main()
// {
//     vector<vector<char>> board = {{'a','b','b'},{'b','z','b'},{'b','b','a'}};
//     Solution a;
//     a.containsCycle(board);
// }


// #include<bits/stdc++.h>
// using namespace std;
// int g = 10005;
// vector<int> f = vector<int>(g, 0);
// class disjoint_set
// {
// private:
//     vector<int> rank = vector<int>(g, 1);//按秩合并需要用到的深度数组

// public:
//     void Init(int n)
//     {
//         for(int i = 0; i < n; ++i) f[i] = i;
//     }

//     int Find(int x)
//     {
//         return  f[x] == x ? x : f[x] = Find(f[x]); //路径压缩
//     }

//     void Union(int x, int y)
//     {
//         x = Find(x);
//         y = Find(y);
//         if(x == y) return;
//         f[y] = x;
//     }

//     bool isSame(int x, int y)
//     {
//         x = Find(x);
//         y = Find(y);
//         return x == y;
//     }

//     void Union_rank(int x, int y)//按秩合并
//     {
//         x = Find(x);
//         y = Find(y);
//         if(rank[x] <= rank[y]) f[x] = f[y];
//         else f[y] = f[x];
//         if(rank[x] == rank[y]) rank[y]++;
//     }

// };

// int main()
// {
//     int n, m, z, x, y;
//     cin >> n >> m;
//     disjoint_set st;
//     st.Init(n);
//     for(int i = 0; i < m; ++i)
//     {
//         cin >> z >> x >> y;
//         if(z == 1)
//         {
//             st.Union(x, y);
//         }
//         else
//         {
//             bool ret = st.isSame(x, y);
//             if(ret) cout << 'Y' << '\n';
//             else cout << 'N' << '\n';
//         }
//     }
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     int n;
//     cin >> n;
//     double max = 0, min = 101.0, t1, t2, t;
//     cin >> t1 >> t2;
//     double sum = t1 + t2;
//     if(t1 > t2)
//     {
//         max = t1, min = t2;
//     }
//     else
//     {
//         max = t2, min = t1;
//     }
//     for(int i = 3; i <= n; ++i)
//     {
//         cin >> t;
//         sum += t;
//         if(t > max) max = t;
//         if(t < min) min = t;
//         printf("%.2lf\n", (sum - min - max)/(i - 2));
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// const int N = 1005;
// int arr[N][N];
// int r;

// int f[N][N];

// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     cin >> r;
//     for(int i = 1; i <= r; ++i)
//     {
//         for(int j = 1; j <= i; ++j)
//         {
//             cin >> arr[i][j];
//         }
//     }
//     for(int i = r; i >= 1; --i)
//     {
//         for(int j = i; j >= 1; --j)
//         {
//             f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + arr[i][j];
//         }
//     }
//     cout << f[1][1];
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int n, V;
// int v[1010], w[1010];
// int f[1010][1010];

// int main()
// {
//     cin >> n >> V;
//     for(int i = 1; i <= n; ++i)
//     {
//         cin >> v[i] >> w[i];
//     }
//     for(int i = n; i >= 1; --i)
//     {
//         for(int j = 0; j <= V; ++j)
//         {
//             if(j < v[i]) f[i][j] = f[i + 1][j];
//             else f[i][j] = max(f[i + 1][j], f[i + 1][j - v[i]] + w[i]);
//         }
//     }
//     cout << f[1][V];
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;

// const int N = 1010;
// int n, v;
// int V[N], W[N];
// int dp[N];

// int main()
// {
//     cin >> n >> v;
//     for(int i = 1; i <= n; ++i) cin >> V[i] >> W[i];
//     for(int i = 1; i <= n; ++i)
//     {
//         for(int j = 0; j <= v; ++j)
//         {
//             if(j < V[i]) dp[j] = dp[j];
//             else dp[j] = max(dp[j], dp[j - V[i]] + W[i]);
//         }
//     }
//     cout << dp[v];
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;

// int N, V, M;
// int m[1010], w[1010], v[1010];
// int dp[1010][110][110];

// int main()
// {
//     cin >> N >> V >> M;
//     for(int i = 1; i <= N; ++i) cin >> v[i] >> m[i] >> w[i];
//     for(int i = 1; i <= N; ++i)
//     {
//         for(int j = 0; j <= V; ++j)
//         {
//             for(int k = 0; k <= M; ++k)
//             {
//                 if(j < v[i] || k < m[i]) dp[i][j][k] = dp[i - 1][j][k];
//                 else dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - v[i]][k - m[i]] + w[i]);
//             }
//         }
//     }

//     cout << dp[N][V][M];
//     return 0;



// #include <bits/stdc++.h>
// using namespace std;
// const int N = 105;
// int n, V;
// int v[N], w[N], s[N];
// int dp[N];

// int main()
// {
//     cin >> n >> V;
//     for(int i = 1; i <= n; ++i)
//     {
//         cin >> v[i] >> w[i] >> s[i];
//     }
//     for(int i = 1; i <= n; ++i)
//     {
//         for(int j = V; j >= 1; --j)
//         {
//             for(int k = 0; k <= s[i]; ++k)
//             {
//                 if(j >= v[i] * k)
//                     dp[j] = max(dp[j], dp[j - v[i] * k] + w[i] * k);
//             }
//         }
//     }
//     cout << dp[V];
// }

// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     long long sum = 0, temp = 0;
//     for(int i = 1; i <= 7; ++i)
//     {
//         cin >> temp;
//         sum += temp;
//     }
//     if(sum > 0)
//     {
//         cout << "IMissYou!" << '\n' << sum;
//     }
//     else
//     {
//         cout << "OvO";
//     }
//     return 0;
// }


// #include<bits/stdc++.h>
// using namespace std;
// typedef long long ll;

// int main()
// {
//     ll a, b , c;
//     cin >> a >> b >> c;
//     ll ans = 1;
//     while(b)
//     {
//         if((b&1) == 1)
//         {
//             ans = (a * ans) % c;
//         }
//         a = (a*a) % c;
//         b >>= 1;
//     }
//     cout << ans;
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;
// int n, c;
// int arr[2005];
// long ans = 0;
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     cin >> n >> c;
//     for(int i = 0 ; i < n; ++i)
//     {
//         cin >> arr[i];
//     }
//     sort(arr, arr + n);
//     for(int i = 0; i < n; ++i)
//     {
//         ans += (upper_bound(arr, arr + n, c + arr[i]) - arr) - (lower_bound(arr, arr + n, c + arr[i]) - arr);
//     }
//     cout << ans;
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;
// const int N = 2e9;
// int n, m, t;
// int arr[N];
// int arrn[2005];
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     cin >> n >> m;
//     for(int i = 0; i < n; ++i)
//     {
//         cin >> arrn[i];
//         ++arr[arrn[i]];
//     }
//     for(int i = 0; i < m; ++i)
//     {
//         cin >> t;
//         ++arr[t];
//     }
//     for(int i = 0; i < n; ++i)
//     {
//         if(arr[arrn[i]] == 2)
//         {
//             cout << arr[i] << " ";
//         }
//     }
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;
// int a, b, c;
// int DayOfYear[15] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
// bool leapYear(int x)
// {
//     return (x % 4 == 0 && x % 100 != 0) || (x % 400 == 0);
// }
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     int a, b, c;
//     scanf("%d/%d/%d", &a, &b, &c);
//     for(int year = 1960; year <= 2059; ++year) {
//         DayOfYear[2] = (leapYear(year) ? 29 : 28);
//         for(int month = 1; month <= 12; ++month)
//             for(int day = 1; day <= DayOfYear[month]; ++day)
//                 if((a == year % 100 && b == month && c == day) ||
//                    (a == month && b == day && c == year % 100) ||
//                    (a == day && b == month && c == year % 100))
//                     printf("%d-%02d-%02d\n", year, month, day); 
//     }
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     int n;
//     cin >> n;
// 	for(int i = 0;i * i <= n;i++){
// 		for(int j = 0;i * i + j * j <= n;j++){
// 			for(int k = 0;i * i + j * j + k * k <= n;k++){
// 				int t = n - i * i - j * j - k * k;
// 				if(sqrt(t) == floor(sqrt(t))){
// 					cout << i << " " << j << " " << k << " " << sqrt(t) << endl;
// 					return 0;
// 				}
// 			}
// 		}
// 	}
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;
// const int N = 35;
// int n, m;
// int dp[N][N];

// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     cin >> n >> m;
//     for(int i = 1; i <= n; ++i)
//         dp[i][1] = 1;
//     for(int i = 1; i <= m; ++i)
//         dp[1][i] = 1;
//     for(int i = 2; i <= n; ++i)
//         for(int j = 2; j <= m; ++j)
//         {
//             if ((!(i&1)) && (!(j&1))) dp[i][j] = 0;
//             else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//         }
//     cout << dp[n][m];
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int ans;
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     int n;
//     cin >> n;
//     ans += n;
//     while(n >= 3)
//     {
//         int t = n / 3;
//         ans += t;
//         n %= 3;
//         n += t;
//     }
//     cout << ans;
//     return 0;
// }




// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     string s;
//     cin >> s;
//     for(int i = 3; i < 7; ++i)
//     {
//         cout << s[i];
//     }
//     for(int i = 0; i < 3; ++i)
//       {
//           cout << s[i];
//       }
//     return 0;
// }

//客气小孩哥
// #include <bits/stdc++.h>
// using namespace std;
// int a, b;
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     cin >> a >> b;
//     int time = 0;
//     while(a > 1 || b > 1)
//     {
//         if(a>=b)
//         {
//             if(a % 2 == 0)
//             {
//                 b += a/2;
//                 a = 0;
//                 time++;

//             }
//             else
//             {
//                 b += (a - 1) / 2;
//                 a = 1;
//                 time++;
//             }
//         }
//         else
//         {
//             if(b % 2 == 0)
//             {
//                 a += b/2;
//                 b = 0;
//                 time++;

//             }
//             else
//             {
//                 a += (b - 1) / 2;
//                 b = 1;
//                 time++;
//             }
//         }
//     }

//     if(time % 2 == 0)
//     {
//         cout << "Alice";
//     }
//     else cout << "Brown";
//     return 0;
// }



// //开着我的小新车
// #include <bits/stdc++.h>
// using namespace std;
// int N, L, x[100005], Q;
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     cin >> N;
//     for(int i = 1; i <= N; ++i)
//         cin >> x[i];
//     cin >> L >> Q;
//     int LL = L * 2;
    
//     for(int i = 0; i < Q; ++i)
//     {
//         int time = 0;
//         int l, r;
//         cin >> l >> r;
//         // if(r != x[N] && (abs(x[r] - x[l]) <= LL)) cout << 1 << '/n';
//         while(l < r)
//         {
//             if(x[l] + L >= x[r])
//             {
//                 time++;
//                 //cout << time << '\n';
//                 break;
//             }
//             int j=l;
//             while(x[j]<x[l]+L)j++;
//             int k=j-1;
//             while(x[k]<x[l]+2*L)k++;
            
//             if(x[l] + L -x[j-1]  >= x[l]+2*L-x[k-1])
//             {
//                 l=k-1;
//                 time+=2;
//             }
//             else
//             {
//                 l=j-1;
//                 time++;
//             }
//         }
//         cout << time << '\n';
//     }

//     return 0;
// }


//翻译1
// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     string S, T;
//     cin >> S >> T;
//     int q; cin >> q;
//     while(q--)
//     {
//         int a, b ,c, d;
//         cin >> a >> b >> c >> d;
//         int cnt_Tx = 0, cnt_Th = 0;
//         int cnt_Sx = 0, cnt_Sh = 0;
//         for(int i = a-1; i < b; ++i)
//         {
//             if(S[i] == 'X')cnt_Sx++;
//             if(S[i] == 'H')cnt_Sh++;
//             if(cnt_Sh > 3)
//                 cnt_Sh -= 3;
//             if(cnt_Sx > 3)
//                 cnt_Sx -= 3;
//         }
//         cnt_Sh += cnt_Sx*2;
//         cnt_Sh %=3;
//         for(int i = c-1; i < d; ++i)
//         {
//             if(T[i] == 'X')cnt_Tx++;
//             if(T[i] == 'H')cnt_Th++;
//             if(cnt_Th > 3)
//                 cnt_Th -= 3;
//             if(cnt_Tx > 3)
//                 cnt_Tx -= 3;
//         }
//         cnt_Th += cnt_Tx*2;
//         cnt_Th%=3;
//         if(cnt_Sh == cnt_Th)
//         {
//             cout << "YES" << '\n';
//         }
//         else cout << "NO" << '\n';
//     }
//     return 0;
// }



// //翻译2
// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     string S, T;
//     cin >> S >> T;
//     int q; cin >> q;
    
//     for(int i = 0; i < q; i++)
//     {
//         string SS = S;
//         string TT = T;
//         int a, b ,c, d;
//         cin >> a >> b >> c >> d;
//         // string SS(&S[a - 1], &S[b]);
//         // string TT(&T[c - 1], &T[d]);
//         sort(&SS[a - 1], &SS[b]);
//         sort(&TT[c - 1], &TT[d]);
//         int l, r;
//         for(int j = a - 1; j < a - 1 + min(b - a, d - c); ++j)
//         {
//             if(SS[j] - TT[j - a + c] != 0)
//             {
//                 l = j;
//                 break;
//             }
//         }
//         for(int j = l; j < l + min(b - a, d - c); ++j)
//         {
//             if(SS[j] - TT[j - a + c] == 0)
//             {
//                 r = j;
//                 break;
//             }
//         }
//         if(r - l == fabs((b - a) - (d - c)))
//         {
//             cout << "YES" << '\n';
//         }
//         else
//         {
//             cout << "NO" << '\n';
//         }
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     string S, T;
//     cin >> S >> T;
//     int q; cin >> q;
    
//     for(int i = 0; i < q; i++)
//     {
//         int a, b ,c, d;
//         cin >> a >> b >> c >> d;
//         string SS(&S[a - 1], &S[b]);
//         string TT(&T[a - 1], &T[b]);
//         sort(SS.begin(), SS.end());
//         sort(TT.begin(), TT.end());
//         int l, r;
//         for(int j = 0; j < min(SS.size(), TT.size()); ++j)
//         {
//             if(SS[i] - TT[i] != 0)
//             {
//                 l = j;
//                 break;
//             }
//         }
//         for(int j = l; j < min(SS.size(), TT.size()); ++j)
//         {
//             if(SS[i] - TT[i] == 0)
//             {
//                 r = j;
//                 break;
//             }
//         }
//         if(r - l == fabs(SS.size() - TT.size()))
//         {
//             cout << "YES" << '\n';
//         }
//         else
//         {
//             cout << "NO" << '\n';
//         }
//     }
//     return 0;
//}

// #include <bits/stdc++.h>
// using namespace std;
// long long a, b, c, x, y;
// int main()
// {
//     int t;
//     cin >> t;
//     while(t--)
//     {
//         cin >> a >> b >> c >> x >> y;
//         if((a >= x) && (b >= y))
//         {
//             cout << "YES" << '\n';
//         }
//         else if((a < x) && (b >= y) && (c >= (x - a)))
//         {
//             cout << "YES" << '\n';
//         }
//         else if((a >= x) && (b < y) && (c >= (y - b)))
//         {
//             cout << "YES" << '\n';
//         }
//         else if((a < x) && (b < y) && (c >= (x - a) + (y - b)))
//         {
//             cout << "YES" << '\n';
//         }
//         else cout << "NO" << '\n';
//     }
//     return 0;
// }



// #include <bits/stdc++.h>
// using namespace std;
// void solve()
// {
//     int n;
//     cin >> n;
//     vector<int> arr(n);
//     for(int i = 0; i < n; ++i) cin >> arr[i];
//     int ans = 0;
//     for(int i = n - 2; i >= 0; --i)
//     {
//         while(arr[i] >= arr[i + 1] && arr[i] > 0)
//         {
//             arr[i] /= 2;
//             ans++;
//         }
//         if(arr[i] == arr[i + 1])
//         {
//             cout << "-1" << '\n';
//             return;
//         }
//     }
//     cout << ans << '\n';
// }
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     int t;
//     cin >> t;
//     while(t--)
//     {
//         solve();
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// const string c = "codeforces";
// int main()
// {
//     int n;
//     cin >> n;
//     while(n--)
//     {
//         int ans = 0;
//         string s;
//         cin >> s;
//         for(int i = 0; i < 10; i++)
//         {
//             if(s[i] != c[i]) ans++;
//         }
//         cout << ans << '\n';
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int t;
//     cin >> t;
//     while(t--)
//     {
//         int ans = 0;
//         int temp = 0;
//         int n;
//         cin >> n;
//         for(int i = 0; i < n; ++i)
//         {
//             int tt;
//             cin >> tt;
//             if(tt == 0) temp++;
//             else if(tt == 1)
//             {
//                 ans = max(ans, temp);
//                 temp = 0;
//             }
//         }
//         ans = max(ans, temp);
//         cout << ans << '\n';
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int t;
//     cin >> t;
//     while(t--)
//     {
//         int n;
//         cin >> n;
//         int t1 = INT_MAX, flag1 = 0;
//         int t2 = INT_MAX, flag2 = 0;
//         int t3 = INT_MAX, flag3 = 0;
//         for(int i = 0; i < n; ++i)
//         {
//             int time = 0;
//             cin >> time;
//             string sk;
//             cin >> sk;
//             if(sk[0] == '1' && sk[1] == '0')
//             {
//                 t1 = min(t1, time);
//                 flag1 = 1;
//             }
//             if(sk[0] == '0' && sk[1] == '1')
//             {
//                 t2 = min(t2, time);
//                 flag2 = 1;
//             }       
//             if(sk[0] == '1' && sk[1] == '1')
//             {
//                 t3 = min(t3, time);
//                 flag3 = 1;
//             }
//         }
//         if(!(flag1 && flag2) && flag3)
//         {
//             cout << t3 << '\n';
//         }
//         else if(flag1 && flag2 && flag3)
//         {
//             if(t3 < t1 + t2) cout << t3 << '\n';
//             else if(t3 > t1 + t2) cout << t1 + t2 << '\n';
//         }
//         else if(flag1 && flag2 && !flag3)
//         {
//             cout << t1 + t2 << '\n';
//         }
//         else
//         {
//             cout << "-1" << '\n';
//         }

//     }
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;
// int dx[4] = {0, 0, 1, -1};
// int dy[4] = {1, -1, 0, 0};
// int dfs(vector<vector<int>>&arr, int x, int y)
// {
//     if(x < 1 || x > arr.size() || y < 1 || y > arr.size()) return 0;
//     if(arr[x][y] == 0) return 0;
//     int ret = 0;
//     if(arr[x][y] != 0)
//     {
//         ret += arr[x][y];
//         arr[x][y] = 0;
//     }
//     for(int i = 0; i < 4; ++i)
//     {
//         ret += dfs(arr, x + dx[i], y + dy[i]);
//     }
//     return ret;
// }
// int main()
// {
//     int t;
//     cin >> t;
//     while(t--)
//     {
//         int n, m;
//         cin >> n >> m;
//         vector<vector<int>> arr = vector<vector<int>>(n+10, vector<int>(m+10, 0));
//         for(int i = 1; i <= n; i++)
//         {
//             for(int j = 0; i <= m; ++j)
//             {
//                 cin >> arr[i][j];
//             }
//         }
//         int ans = 0;
//         for(int i = 1; i <= n; ++i)
//         {
//             for(int j = 1; j <= m; ++j)
//             {
//                 ans = max(ans, dfs(arr, n, m));
//             }
//         }
//     }

//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// int cnt[30];
// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     int maxt = 0;
//     for(int i = 0; i < 4; i++)
//     {
//         string s;
//         getline(cin, s);
//         for(int j = 0; j < s.size(); j++)
//         {
//             if(s[j] <= 'Z' && s[j] >= 'A') cnt[s[j] - 'A']++;
//             maxt = max(maxt, cnt[s[j] - 'A']);
//         }
//     }
//     int top = maxt;
//     for(int i = 1; i <= maxt; ++i)
//     {
//         for(int j = 1; j <= 51; ++j)
//         {
//             if(!(j&1)) cout << ' ';
//             else
//             {
//                 if(cnt[j/2] < top) cout << ' ';
//                 else
//                 {
//                     cout << '*';
//                 }
//             }
//         }
//         top--;
//         cout << '\n';
//     }
//     for(int i = 1; i <= 51; ++i)
//     {
//         if(!(i&1)) cout << ' ';
//         else cout << (char)('A' + (i/2));
//     }
//     return 0;
// }



// #include <bits/stdc++.h>
// using namespace std;

// int kmp(string text, string pattern) {
//     int n = text.size(), m = pattern.size();
//     if (m == 0) {
//         return 0;
//     }
//     vector<int> next(m);
//     for (int i = 1, j = 0; i < m; i++) {
//         while (j > 0 && pattern[i] != pattern[j]) {
//             j = next[j - 1];
//         }
//         if (pattern[i] == pattern[j]) {
//             j++;
//         }
//         next[i] = j;
//     }
//     for (int i = 0, j = 0; i < n; i++) {
//         while (j > 0 && text[i] != pattern[j]) {
//             j = next[j - 1];
//         }
//         if (text[i] == pattern[j]) {
//             j++;
//         }
//         if (j == m) {
//             return i - m + 1;
//         }
//     }
//     return -1;
// }

// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    
//     cout << ans;
// }


// #include <bits/stdc++.h>
// using namespace std;

// //kmp算法
// vector<int> prefix_function(string s) {
//   int n = (int)s.length();
//   vector<int> pi(n);
//   for (int i = 1; i < n; i++) {
//     int j = pi[i - 1];
//     while (j > 0 && s[i] != s[j]) j = pi[j - 1];
//     if (s[i] == s[j]) j++;
//     pi[i] = j;
//   }
//   return pi;
// }

// //查找字串
// vector<int> find_occurrences(string text, string pattern) {
//   string cur = pattern + '#' + text;// # 为两个字符串中都不可能出现的字符
//   int sz1 = text.size(), sz2 = pattern.size();
//   vector<int> v;//记录子串在母串中出现的下标
//   vector<int> lps = prefix_function(cur);
//   for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
//     if (lps[i] == sz2) v.push_back(i - 2 * sz2);
//   }
//   return v;
// }

// int main()
// {
//     string s1 = "123456789789578";
//     string s2 = "78";
//     vector<int> ret = find_occurrences(s1, s2);//s1中找s2
//     for(auto i : ret)
//     {
//         cout << i << ' ';
//     }
// }


// #include <bits/stdc++.h>
// using namespace std;

// int main() {
//     string s1, s2;
//     cin >> s1 >> s2;
//     string ans;
//     for(int i = 0;i < s1.size(); ++i)
//     {
//         bool flag = 1;
//         for(int j = 0; j < s2.size(); ++j)
//         {
//             if(s1[i] == s2[j])
//             {
//                 flag = 0;
//                 break;
//             }
//         }
//         if(flag)
//         {
//             ans.push_back(s1[i]);
//         }
//     }
//     cout << ans;
//     return 0;
// }



// #include <bits/stdc++.h>
// using namespace std;

// int lcm(int x, int y)
// {
//     return x/__gcd(x, y)*y;
// }

// void solve()
// {
//     int x, y;
//     cin >> x >> y;
//     int lc = lcm(x, y);
//     int gc = __gcd(x, y);
//     if(lc == 1 && gc == 1)
//     {
//         cout << 1 << ' ' << 1 << '\n';
//         return;
//     }
//     for(int i = 1; i*i < x*y; ++i)
//     {
//         for(int j = 1; j*j < x*y; ++j)
//         {
//             if(sqrt(lc/gc) == sqrt(j)*i)
//             {
//                 cout << i << ' ' << j << '\n';
//                 return;
//             }
//         }
//     }
// }

// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     int t;
//     cin >> t;
//     while(t--)
//     {
//         solve();
//     }
//     return 0;
// }



// #include <bits/stdc++.h>
// using namespace std;

// int dx[6] = {-1, 0, 1, 0, 0}, dy[6] = {0, 1, 0, -1, 0};
// char g[6][6], bup[6][6];

// void turn(int x, int y)
// {
//     for(int i = 0; i < 5; ++i)
//     {
//         int tx = x + dx[i], ty = y + dy[i];
//         if(tx >= 0 && tx < 5 && ty < 5 && ty >= 0)
//         {
//             g[tx][ty] ^= 1;
//         }
//     }
// }

// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     int t;
//     cin >> t;
//     while(t--)
//     {
//         for(int i = 0; i < 5; i++)
//             cin >> g[i];
//         int ans = 100;
//         for(int op = 0; op < 32; ++op)
//         {
//             memcpy(bup, g, sizeof(g));
//             int step = 0;
//             for(int i = 0; i < 5; ++i)
//             {
//                 if(op >> i & 1)
//                 {
//                     step++;
//                     turn(0, i);
//                 }
//             }
//             for(int i = 0; i < 4; ++i)
//             {
//                 for(int j = 0; j < 5; ++j)
//                 {
//                     if(g[i][j] == '0')
//                     {
//                         step++;
//                         turn(i + 1, j);
//                     }
//                 }
//             }
//             bool d = 0;
//             for(int i = 0; i < 5; ++i)
//             {
//                 if(g[4][i] == '0')
//                 {
//                     d = 1;
//                     break;
//                 }
//             }
//             if(!d) ans = min(ans, step);
//             memcpy (g, bup, sizeof g);
//         }
//         if(ans > 6) ans = -1;
//         cout << ans << '\n';
//     }
//     return 0;
// }


// #include <bits/stdc++.h>
// using namespace std;
// const int N = 1e5 + 5;
// map<pair<long long, long long>, long long> a;

// void solve()
// {
//     int t;
//     vector<long long> tt;
//     while(cin >> t)
//     {
//         tt.push_back(t);
//         if(cin.get() == '\n')
//             break;
//     }
//     if(tt.size() == 4)
//     {
//         if(tt[3] != 0)
//         {
//             pair<long long, long long> id = {tt[1], tt[2]};
//             a[id] += tt[3];
//         }
//         else
//         {
//             pair<long long, long long> id = {tt[1], tt[2]};
//             a[id] = 0;
//         }
//     }
//     if(tt.size() == 3)
//     {
//         pair<long long, long long> id = {tt[1], tt[2]};
//         if(a.count(id))
//             cout << a[id] << '\n';
//         else
//             cout << 0 << '\n';
//     }
// }

// int main()
// {
//     int n, q;
//     cin >> n >> q;
//     while(q--)
//     {
//         solve();
//     }
//     return 0;
// }


// #include <bits/stdc++.h>

// using namespace std;
// int n,q,p,k;
// map<long long,int>b;
// long long i,j;
// int main()
// {
// 	scanf("%d%d",&n,&q);
// 	while(q--)
// 	{
// 		scanf("%d%d%d",&p,&i,&j);
// 		if(p==1)
// 		{
// 			scanf("%d",&k);
// 			b[i*1000000+j]=k;
// 		}
// 		else printf("%d\n",b[i*1000000+j]);
// 	}
// 	return 0;
// }


// #include <iostream>
// using namespace std;

// typedef struct st
// {
// private:
//     int _a;
//     void init(const int a)
//     {
//         _a = a;
//     }
// }st;


// void solve()
// {
//     st s;
//     // s.init(5);
//     // cout << s._a;
// }

// int main()
// {
//     int t;
//     cin >> t;
//     while(t--)
//     {
//         solve();
//     }
//     return 0;
// }









